#include <vector>
#include <iostream>
#include <unordered_map>

using namespace std;

class Solution {
public:
    /**
     * 这题目有点类似于求数组中两个数字和为 k 的次数，
     * 关键点在于找到方程能够描述 f(i, j) 和 k 的关系
     * 
     * 比如两个数字和为 k，那么 f(i, j) = nums[i] + nums[j]，
     * 代入题目中即求 f(i, j) = nums[i] + nums[j] = k，
     * 那么可以在遍历数组的时候，通过哈希表查找 k - nums[i] 是否出现过，
     * 同时在哈希表记录这次 nums[i]
     * 
     * 对于这个题目，题中描述为连续子数组的和，
     * 那么对于任意子数组的和，假设 i <= j，j 为当前的索引，
     * f(i, j) = prefixSum[j] - prefixSum[i - 1] = k，
     * 那么在遍历的过程中查找 prefixSum[j] - k 是否出现过，
     * 注意在 j 为 0 的时候，prefixSum[-1] 并不存在，
     * 因此要在开始前，哈希表记录前缀和为 0 的出现 1 次
     * 
     * 时间复杂度：O(N)
     */
    int subarraySum(vector<int>& nums, int k) {
        int ans = 0;
        int prefixSum = 0;

        unordered_map<int, int> m;
        m[0] = 1;

        for (int &num: nums) {
            prefixSum += num;
            if (m.find(prefixSum - k) != m.end()) {
                ans += m[prefixSum - k];
            }
            m[prefixSum]++;
        }

        return ans;
    }
};

int main() {
  vector<int> nums = { 1, 2, 3 };

  int k = 3;

  cout <<  Solution().subarraySum(nums, k) << endl;

  return 0;
}
